Verkle trees
Verkle treeはまだ新しいアイデアで、John Kuszmaulが2018年のこの論文で初めて紹介したもの
Verkle treesはMerkle treesと同じように大量のデータをVerkle treesに入れて、ツリーのルートだけを持っている人が検証できるようなproofを作成できるデータ構造
Merkle Treeと違ってProof検証に必要なデータサイズが定数で良い
木に10億個のデータが含まれている場合、従来のバイナリMerkle木で証明を行うと約1キロバイトが必要だが、Verkle treesでは150バイト以下になる
これは、ステートレス・クライアントを最終的に実用化するのに十分な削減
証明者は、各レベルですべての「姉妹ノード」を提供する必要がない代わりに、各リーフノードからルートへのパスに沿ったすべてのコミット間のすべての親子関係を証明する単一の証明を提供するだけでよい。
これにより、証明サイズは、理想的なMerkle treeと比較して6～8倍、Ethereumが現在使用しているヘキサリーパトリシアツリーと比較して20～30倍以上小さくなるらしい
中期的には、SNARKによってさらに改善することができる
すでに効率的なVerkle proofの検証者をSNARKして、proofのサイズをほぼゼロにすることもできまるし、SNARKがさらに改善された場合には、SNARKしたMerkle proofに切り替えることもできる
量子コンピューティングの台頭により、Verkle treeが依存している線形同型性が安全ではなくなるため、ハッシュを用いたSTARKed Merkle proofに変更せざるを得なくなるかも
Merkle Patricia vs Verkle Tree node structure
すべてのノードは、(i)空、(ii)キーと値を含むリーフノード、(iii)ある固定数の子を持つ中間ノード（木の「幅」）のいずれか
中間ノードの値は，その子ノードの値のハッシュとして計算される．
下の図では，キーが4ccのノードに行くには，ルートから始めて，4の位置の子に行き，次にcの位置の子に行き，再びcの位置の子に行く（16進法ではc=12）
baaaのノードに行くには，ルートのbの位置の子に行き，次にそのノードのaの位置の子に行く
パス(b,a)のノードには、キー baaa を持つノードが直接含まれている
これは、ツリー内に ba で始まる他のキーが存在しないため
https://scrapbox.io/files/60fe0f517a0f85001c3369aa.png
ヘキサリー（親ごとに16の子）のノードの構造。ここでは6つの（キー、値）ペアで満たされています。
Verkle treesとMerkle Patricia treesの構造の唯一の違いは、実際にはVerkle treesのほうが幅が広いということ
Merkle Patricia treesは、幅＝2のときに最も効率的
（そのため、Ethereumのヘキサリーパトリシアツリーは、実際にはかなり最適ではない）
Verkle treesは、幅が大きくなるほど証明が短くなる
唯一の限界は、幅が大きくなりすぎると証明の作成に時間がかかりすぎること
Commitments and proofs
Merkle trees（Merkle Patricia treesを含む）では、値の証明は姉妹ノードのセット全体で構成される
proofには、証明しようとしているノードに降りていくパスのいずれかのノードと親を共有する、ツリー内のすべてのノードが含まれていなければならない
ノードの値を計算するには、そのノードの子のセット全体が必要なので、各レベルで姉妹ノードを提供する必要があり、これをルートにたどり着くまで続ける必要がある
もしこの木に256個のランダムに割り当てられたノードがあったとしたら，最上層はほぼ確実に16個のノードすべてが満杯になり，第2層は平均して約63.3%満杯になる
https://scrapbox.io/files/60fe0f80a9e7a9001cd1b9f9.png
Merkle treesにおける4ceポジションの値の証明の図(証明に含まれなければならない姉妹ノードは赤でハイライト)
Verkle treesでは、姉妹ノードを提供する必要はなく、パスを提供するだけで、証明のために少し余分なものを提供する
これが、Verkle treesが幅を大きくすることで利益を得て、Merkle Patricia treesがそうでない理由
内側のノードとその子を計算するために特別なハッシュ関数を使い、これを実現している
具体的には、ベクトル・コミットメントが使われている
これはリスト$ h(z_1,z_2,・・・,z_n)→C をハッシュ化するもの
ベクトルコミットは、コミットCとi番目の位置の値$ z_iに対して、あるリストへのコミットCであることを簡単に証明できる
Verkle proofでは、この短いproofがMerkle Patriciaのproofにおける姉妹ノードの機能を置き換え、子ノードが本当に親ノードの与えられた位置にある子であるという確信を検証者に与える
パス自体に加えて、パス内の各コミットメントを次のコミットメントにリンクするためのいくつかの短いproofだけでよい
https://scrapbox.io/files/60fe0fa4dcb278001c570ab8.png
実際には、ベクトルコミットメントよりもさらに強力なプリミティブである「多項式コミットメント」を使用する
これは多項式をハッシュ化し，そのハッシュ化された多項式を任意の時点で評価できることを証明できるもの
標準化された座標のセット$ (c_1,c_2,・・・,c_n) に合意した場合、リスト$ (y_1,y_2,・・・,y_n) が与えられれば、$ P(c_i)=y_i for all$ i∈[1... .n]という多項式Pにコミットすることができる
この多項式はラグランジュ補間で求めることができる
最も簡単に使える2つの多項式コミットメントスキームは、KZGコミットメントとbulletproof-styleコミットメント
どちらの場合も、コミットメントは1つの32-48バイトの楕円曲線ポイント
KZGコミットメントを使用した場合、proofサイズは中間ノードあたり96バイトとなり、幅を256とした場合の単純なMerkle proofと比較して、約3倍のスペース効率が得られる
さらにスペース効率を向上させることができるらしい
Merging the proofs
パスに沿った各コミットメントに対して1つの証明を必要とする代わりに、多項式コミットメントの追加特性を利用することで、パスに沿ったコミットメント間のすべての親子関係を証明する固定サイズの証明を、無制限の数のキーに対して1つ作ることができます。これには、ランダムな評価によって多重証明を実現する方式を用います。
しかし，この方式を使うためには，まず問題をより構造的なものに変換する必要があります．Verkle treeには、1つ以上の値の証明があります。この証明の主要部分は、各ノードへのパスに沿った中間ノードで構成されています。各ノードについて、そのノードが実際にその上のノードの子であること（そして正しい位置にあること）も証明しなければなりません。上記の単一値の証明の例では、証明するための証明が必要でした。
key:4ceノードが実際にprefix.4c中間ノードのposition-e childであること。
prefix:4c中間ノードが実際にprefix: 4c中間ノードの位置-cの子供であること。
4中間ノードの位置-cの子であること。その prefix:4中間ノードが実際にはルートの位置-4の子であること
もし、複数の値（例えば、4ceと420の両方）を証明するproofがあれば、さらに多くのノードとさらに多くのリンクが必要になります。しかし、いずれにしても、私たちが証明しているのは、「ノードAは実際にノードBのposition-i childである」という形式のステートメントのシーケンスです。多項式コミットメントを使っている場合、これは方程式に変わります。$ A(x_i)=y、ここでyはBへのコミットメントのハッシュである。
この証明の詳細は技術的なもので、私よりもDankrad Feist氏の方がよく説明してくれています。証明生成の中で最も大がかりで時間のかかるステップは、次のような形式の多項式を計算することです。
$ g(X)=r^0\frac{A_0(X)-y_0}{X-x_0}+r^1\frac{A_1(X)-y_1}{X-x_1}+・・・+r^n\frac{A_n(X)-y_n}{X-x_n}
各項の$ r^i\frac{A_i(X)-y_i}{X-x_i}を計算することができるのは、その式が（分数ではなく）多項式の場合だけです。そのためには、$ A_i(x)が点$ x_iで等しくなる必要があります。
これを例で見てみましょう
$ A_i(X)=X^2+X+3
$ (x_i=2,y_i=9)を証明する。$ A_i(2)が9と等しければ、これは機能する
$ A_i(X)-9=X^2+X-6と$ \frac{X^2+X-6}{X-2}は$ X-3を提供する
しかし、$ (x_i=2,y_i=10) を入れようとすると、$ X^2+X-7 は$ X-2 の端数がないときれいに割り切れないので、うまくいきません。
証明の残りの部分は、多項式のコミットメントを提供し、そのコミットメントが実際に正しいことを証明することになります。繰り返しになりますが、証明の残りの部分についてはDankradのより技術的な説明を参照してください。
https://scrapbox.io/files/60fe1474747ff3001c08f103.png
1つの証明で、無限の親子関係を証明することができます。
以上が、最大効率のVerkle証明の姿です。
Key properties of proof sizes using this scheme
Dankradの多項式評価証明では、証明者は、各$ A_iに対するコミットメントと証明される値が与えられれば、任意の数の評価$ A_i(x_i)=y_iを証明することができます。この証明は一定のサイズ（1つの多項式の約束、1つの数値、2つの証明、使用するスキームに応じて128～1000バイト）です。
$ y_iの値は、Verkle証明の他の値から直接計算できるので、明示的に指定する必要はありません。それぞれの$ y_iは、パスの次の値（コミットメントまたはリーフ）のハッシュそのものです。
パス（したがって$ x_iの値）は、キーとパスから得られる座標から計算できるので、$ x_iの値も明示的に提供する必要はありません。したがって、必要なのは、証明する葉（キーと値）と、各葉から根へのパスに沿った約束事だけです。
幅256の木で、$ 2^{32}個のノードがあると仮定すると、証明には、証明するキーと値に加えて、各値の、その値からルートまでのパスに沿った（平均して）3つのコミットメントが必要になります。
多くの値を証明する場合は、さらに節約できます。証明する値の数にかかわらず、トップレベルの256個以上の値を提供する必要はありません。
Proof sizes (bytes). Rows: tree size, cols: key/value pairs proven
https://scrapbox.io/files/60fe18b49be828001cb82cae.png
幅256、48バイトのKZGコミットメント/プルーフを想定しています。現実的なランダムツリーの場合は、深さを約0.6倍にしてください（1要素あたり約30バイト）。KZGの代わりにBulletproofスタイルのコミットを使用する場合は、32バイトにしても問題ないので、これらのサイズは1/3に減らすことができます。
Prover and verifier computation load
証明を生成するためのコストの大部分は、各$ r^i\frac{A_i(X)^y_i}{X-x_i}の計算
これには、木の幅の約4倍のフィールド演算（256ビットのモジュラー演算）が必要
これが、Verkle木の幅を制限する主な制約です。
幸いなことに、4回のフィールド演算は小さなコストです。
楕円曲線の乗算1回には、通常、数百回のフィールド演算が必要です。
したがって、Verkle treeの幅は非常に高くすることができ、幅256～1024が最適な範囲と思われます。
木を編集するには，葉から根に向かって「木を上る」必要があり，各ステップで中間のコミットメントを変更して，下の方で起こった変更を反映させる．
幸いなことに、各コミットメントを最初から計算し直す必要はありません。
多項式のコミットメント$ C=com(F)があれば，$ C'=C+com(G)を取ることで$ C'=com(F+G)を計算することができます．
ここでは、$ G=L_i*(v_{new}-v_{old})としていますが、ここでは、変更しようとしている位置では1、それ以外の場所では0になる多項式の事前に計算された約束事です。
したがって、1回の編集には約4回の楕円曲線の乗算が必要になりますが（リーフとルートの間のコミットメントごとに1回、今回はルートも含む）、各$ L_iの倍数を事前に計算して保存しておくことで、これらの計算を大幅に短縮することができます。
証明の検証は非常に効率的です。N個の値の証明に対して、検証者は以下のステップを行う必要がありますが、これらのステップは数千個の値であっても100ミリ秒以内で行うことができます。
1つのサイズNの楕円曲線の高速線形結合
約4N個のフィールド演算（256ビットのモジュール式算術演算など
証明の大きさに依存しない小さな一定量の作業
また、Merkle Patricia proofと同様に、Verkle proofは、証明されているツリーの値を変更し、変更後の新しいルートハッシュを計算するのに十分な情報を検証者に与えることに注意してください。
これは、例えばブロック内の状態変更が正しく処理されたかどうかを検証するために重要